COMMENT ⊗   VALID 00004 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	~[CαGEOMETRIC MODELING THEORY.
C00004 00003	[1.1	Kinds of Geometric Models.]
C00006 00004		For a naive start,  first consider a  3-D array in which each
C00010 ENDMK
C⊗;
~[C;αGEOMETRIC MODELING THEORY.;
λ30;I425,0;P5;JCFA             SECTION 1.
~JCFD                  GEOMETRIC MODELING THEORY.
~I950,0;JUFA
[1.0	Introduction to Geometric Modeling.]

	In  the specific  context of  computer  vision and  graphics,
geometric modeling refers to constructing computer representations of
physical objects,    cameras,   images  and  light for  the  sake  of
simulating their  behavior. In  Artificial Intelligence,  a geometric
model is  a kind of world model; ignoring subtleties, geometric world
modeling is distinguished from semantic and logical world modeling in
that  it is quantitative  and numerical  rather than  qualitative and
symbolic.  The  notion of a  world model requires  an external  world
environment to be modeled,  an internal  computer environment to hold
the  model,   and a  task performing  entity  to use  the model.   In
geometry,  modeling is a synthetic problem,  like a construction with
ruler  and straight  edge, modeling  problems require  an algorithmic
solution  rather than a  proof. The adjective  "geometric" however is
quite apropos  in that it  literally means  "world measure" which  is
exactly the activity to be automated.
~Q;F.
[1.1	Kinds of Geometric Models.]

	The main  problem  of geometric  modeling is  to invent  good
methods for representing  arbitrary physical objects in a computer. A
physical object (for the moment) is something solid, rigid,   opaque,
Newtonian and macroscopic with a mathematically well behaved surface.
Physical objects  include: the earth, chairs, roads,  and plastic toy
horses.  Physical objects may be  moved about in space,
but two objects  can not simultaneously occupy the  same space at the
same time.  The scope of the problem can be appreciated by  examining
the virtues and drawbacks of the kinds of models listed in box 1.1 below.
~|-----------------------------------------------------------λ10;JAFA
BOX 1.1~JCFA   TEN KINDS OF GEOMETRIC MODELS.
~↓F.
Space Oriented:
	1. 3-D Space Array.
	2. Recursive Cells.
	3. 3-D Density Function.
	4. 2-D Surface Functions.
	5. Parametric Surface Functions.
~↑W640;F.
Object Oriented:
	6. Manifolds.
	7. Polyhedra.
	8. Volume Elements.
	9. Cross Sections.
 	10. Skeletons.
~W0,1260;|---------------------------------------------------λ30;JUFA

	For a naive start,  first consider a  3-D array in which each
element indicates  the presence or absence of  solid matter in a cube
of space.  Such a 3-D  space array has the very desirible  properties
of "spatial addressing" and "spatial uniqueness" in their most direct
and  natural form. Spatial addressing refers  to finding out what the
model  contains  within a  distance  R  of  a  locus  X,Y,Z;  spatial
uniqueness refers  to modeling the property that  physical solids can
not occupy the same space. The  main drawback of the 3-D space  array
model is illustrated by the apparently legal FORTRAN statement:
~JC;F.DIMENSION SPACE(10000,10000,10000)
	The  problem with  such  a  dimension  statement is  that  no
present  day  computer memory  is  large enough  to  contain  a 10↑15
element  array. Smaller  space  arrays  arrays  can  be  useful  but
necessarily  can not  model  large volumes  with  high resolution.  A
further drawback of space arrays is that objects and surfaces are not
readily accessible  as  entities; that  is a  space  array lacks  the
desirible property of "object coherence".

	The space array  idea can be salvaged because  large portions
of the  array contain similar values. By  grouping blocks of elements
with the same values together,   the addressing process becomes  more
complicated but  the overall memory  required is reduced and  the two
desired  properties can be  maintained. One way of  doing this (which
has been  discovered in several  applications) is "recursive  cells";
the  whole space  is considered to  be a  cell; if  the space  is not
homogeneous than  the first  cell is  divided into  two (or  four  or
eight) sub cells and  the criterion is applied again.  This technique
of recursive  celling allows the spatial sorting  of objects,  if the
object models can be subdivided at each recursion without  losing the
properties of the objects.